(1) Field of the Invention
The invention pertains to the field of allocating vehicles to persons desiring transportation
(2) Description of the Related Art
Providers of surface transportation are faced with the problem of carrying independent passengers from separate origins to separate destinations using a limited number of vehicles. Such providers wish to deliver their passengers within the shortest possible time, and to minimize the time, distance, or cost accrued by the vehicles and by the passengers they serve.
Most schemes for delivery of passengers involve either fixed, prearranged routes, or the on-demand service of single passengers. In the case of fixed routes (typically served by buses, but also including trains, airplanes, or other vehicles), a passenger must find a carrier that is traveling to the general area of his destination, and he must arrange to embark at a prearranged time and fixed place. The carrier must also commit resources (vehicles and operators) to routes without knowing in advance if any passengers need to be served, or if the vehicles employed are sufficient to carry the number of passengers desiring travel. Vehicles on fixed routes do have the advantage of carrying multiple unrelated passengers at a time, harvesting lower costs per passenger; however, the passenger's overall journey is usually completed slowly because the passengers' travel plans must be matched with the fixed routes and schedules of the provider.
On the other hand, on-demand transportation (notably taxicabs) is available more quickly, but providers are less able to carry passengers with different origins or destinations in the same vehicle at the same time. Moreover, such providers usually lack an efficient method for allocating vehicles to passengers in such a way that minimizes both passenger travel time and the time the vehicles must travel to serve them, which increases the cost of the service significantly, and the time it takes for the passengers to receive service. While it would behoove such providers to reduce costs by carrying passengers with different origins and/or destinations in the same car—essentially, sharing a car—they struggle to do so while at the same time delivering prompt service to all of their passengers. In particular, they find it difficult to allocate the vehicles available among the persons desiring service. Even if the carriers are able to allocate passengers among vehicles in advance, any new passengers requesting service while the vehicles are already enroute may not receive service until after the vehicles serve all the current passengers; and new vehicles coming into service when existing vehicles are already serving passengers might not be deployed promptly. Moreover, passengers on a vehicle suffering a breakdown, or designated to be served by a vehicle which breaks down (or is otherwise rendered unavailable) before meeting them are left without effective service by carriers operating using existing methods.
Numerous attempts have been made to streamline transportation by better matching travelers with vehicles. One such attempt is described in DE102010003610 A1 (Barnickel, et. al., hereafter “Barnickel”). Barnickel's approach is to permit a driver to designate a range of times or distances within which s/he is willing to detour to pick up an additional passenger. Passengers specify either a time to be picked up or dropped off, or range of “tolerances” (describing ranges either of time or of place) within which they would be willing to accept a ride from a carpool provider. This approach suffers a disadvantage in that the passenger is not guaranteed a ride if the tolerances do not match: if the only car available cannot make the pickup within the passenger's range of tolerances, the passenger is denied service. Barnickel's approach does not seek to optimize either passenger travel time or the car's driving time: rather, it either permits or denies rides on the basis of meeting certain fixed criteria. If several rides fit Barnickel's criteria, Barnickel's approach will not choose the best match among them, but will merely make one or more minimally acceptable matches. If a new car becomes available after a passenger has been matched with a car, Barnickel's method will not allocate that car to that passenger, even if doing so would provide superior service.
U.S. Pat. No. 5,214,689 A (O'Sullivan) describes a method of matching passengers with vehicles, but requires that the vehicles transit a fixed station, and that passengers either embark or disembark there.
U.S. Pat. No. 6,751,548 B2 (Boulard and Fox) describes a ride matching scheme that makes use of straight-line distance between points. This is not the same as using time as calculated by speed limits or other road information. In cases where actual distance traveled varies from straight-line distance (such as in rides spanning both sides of a river, with the nearest bridge at some distance), this method will suffer inaccuracy and fail to deliver optimal efficiency.
U.S. Pat. No. 7,080,019 B1 (Hurzeler) describes a method by which people traveling may locate other people traveling in the same area. It does not permit rerouting of vehicles already in motion, and does not guarantee that an acceptable match will be made even if vehicles are active.
Likewise U.S. Pat. No. 4,360,875 A (Behnke) can similarly leave a passenger standing if an acceptable match cannot be found. This can occur even if a car is available to take passengers. Moreover, Behnke's method requires that the geographic area to be served is partitioned into a grid, and the grid squares are used to inform the matching process. This procedure is prone to inefficiency and error because cities and landscapes are not well modeled by rectangular grids.
U.S. Pat. No. 5,272,638 A (Lineberry, et. al.) proposes a method for optimizing travel along a route containing a series of waypoints (“destinations”), but does not support the notion of a passenger or other load (e.g. cargo) that must be picked up at one location and dropped off at another, and is thus inapplicable to a situation in which persons or goods are transported from Point A to Point B, with Point B necessarily coming later than Point A.
The invention of U.S. Pat. No. 5,604,676 A (Penzias) reports a plurality of paths and prices to the passenger, who must pick one, entailing a certain complexity and delay.
U.S. Pat. No. 8,438,118 B2 (Ho) covers a method to improve transportation of “items or packages” by seeking a more efficient route, and by consolidating shipments. Ho's method requires “time attributes” to function, these being windows or ranges of time within which a package can be picked up or delivered, similar to Barnickel's “tolerances”, and undesirable for the same reasons. At no point does Ho describe his system as being suitable for moving people rather than objects.
The academic literature contains a paper on efficient vehicle routing (Algorithms for Capacitated Vehicle Routing, Charikar et. al., SIAM J. Computing, Vol. 31, No. 3, pp. 685-682, hereafter “Charikar”). Charikar describes mathematical methods for minimizing the distance traveled by a vehicle delivering “pegs” from origins to destinations. Charikar's algorithms all are focused on reducing distance traveled by the delivery vehicle, but do not minimize either time or distance for the cargo (“pegs”). Charikar's methods all assume the vehicles will begin and end their journeys at the same place, which places this optimization problem into a category well recognized by persons skilled in the art of computer science as “NP-complete”. Such problems are for all practical purposes mathematically impossible to solve for any but a small number of vehicles and pegs, which means Charikar's methods are impractical for any but a very small number of pegs.